package com.java.comprehensive.other.sort;

/**
 * @Author: Dgg
 * @Date: 2021/10/11 21:47
 */
public class Shell {
    /**
     * 希尔排序
     */
    public static void sort(Comparable[] comparables) {
        //1、根据comparables 的长度 确定 偏移量h的值
        int h = 1;
        while (h < comparables.length / 2) {
            h = 2 * h + 1;
        }

        //2、希尔排序
        while (h >= 1) {
            //排序
            //2.1找到待插入的元素
            for (int i = h; i < comparables.length; i++) {
                //2.2把带插入的元素插到有序数列中
                for (int j = i; j > h; j -= h) {
                    if (SortUtil.greater(comparables[j - h], comparables[j])) {
                        //交换元素
                        SortUtil.exch(comparables, j - h, j);
                    } else {
                        break;
                    }
                }
            }
            //减小h值
            h = h / 2;
        }
    }
    /**有问题*/
    public static void shellSort(int array[]) {
        for (int step = array.length / 2; step > 0; step /= 2) {
            for (int i = step; i < array.length; i++) {
                int value = array[i];
                int j;
                for (j = i - step; j >= 0 && array[i] > value; j /= step) {
                    array[j + step] = array[j];
                }
                array[j + step] = value;
            }
        }
    }
}
